import java.util.*;

class Solution {
    public int numberOfArithmeticSlices2(int[] nums) {
        // 创建dp表、初始化、填表、返回值
        int n = nums.length;
        int[][] dp = new int[n][n];

        // 初始化为0，而默认就是0，因此无需处理
        
        int ret = 0;
        // 固定最后一个数，枚举倒数第二个数
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                long a = ((long)2 * nums[j] - (long)nums[i]); // 可能出现计算结果溢出的情况
//                long a = 2 * nums[j] - nums[i]; // 错误的处理

                // 遍历找倒数第三个数
                // 可能存在多个 a，都需要统计到 dp[j][i] 中
                // 因为都是以 j，i位置为结尾的子序列且满足等差性质 
                for (int k = j-1; k >= 0; k--) {
                    if (nums[k] == a) {
                        dp[j][i] += dp[k][j] + 1;
                    }
                }
                // 统计
                ret += dp[j][i];
            }
        }

        return ret;
    }


    public static void main(String[] args) {
//        System.out.println(new Solution().numberOfArithmeticSlices(new int[]{
//                0,2000000000,-294967296
//        }));

//        System.out.println(new Solution().numberOfArithmeticSlices(new int[]{
//                2,4,6,8,10
//        }));

        System.out.println(new Solution().numberOfArithmeticSlices(new int[]{
                7,7,7,7,7
        }));
    }


    public int numberOfArithmeticSlices(int[] nums) {
        // 创建dp表、初始化、填表、返回值
        int n = nums.length;
        int[][] dp = new int[n][n];

        // 初始化为0，而默认就是0，因此无需处理

        // 将 原始数组的值 和 下标数组 绑定到一起
        Map<Long, List<Integer>> hash = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (hash.get((long)nums[i]) == null) {
                hash.put((long) nums[i], new ArrayList<>());
            }
            hash.get((long)nums[i]).add(i);
        }

        int ret = 0;
        // 固定最后一个数，枚举倒数第二个数
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                long a = ((long)2 * nums[j] - (long)nums[i]); // 可能出现计算结果溢出的情况
                // 遍历找倒数第三个数
                // 可能存在多个 a，都需要统计到 dp[j][i] 中
                // 因为都是以 j，i位置为结尾的子序列且满足等差性质
                List<Integer> list = hash.get(a);
                if (list != null) {
                    for (int k : list) {
                        if (k < j) { // 要满足 小于 j
                            dp[j][i] += dp[k][j] + 1;
                        } else {
                            // 由于添加下标时是按照 0~n-1 的范围来添加的
                            // 因此下标数组中存放的值一定是有序的（从小到大）
                            break;
                        }
                    }
                }
                // 统计
                ret += dp[j][i];
            }
        }

        return ret;
    }
}